package com.frank.leetcode.question_1_5;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * https://leetcode-cn.com/problems/longest-palindromic-substring/description/
 * 5. 最长回文子串
 * 难度: 中等
 * <p>
 * Question :
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
 * <p>
 * Demo 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba"也是一个有效答案。
 * Demo 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * <p>
 * Created by zhy on 2018/6/1.
 */
public class LongestPalindrome {
    private static Logger LOG = LoggerFactory.getLogger(LongestPalindrome.class);

    @Test
    public void run() {
        long st = System.currentTimeMillis();
        String[] tests = new String[]{"babadada", "ac", "abcb", "aaa", "aaaaa", "aaaaaaaa", "bbc", "abac", "babad", "abcda"};
        int s = 1;
        switch (s) {
            case 1:
                for (String str : tests) {
                    System.out.println("--------------------------------------------");
                    String val = longestPalindrome(str);
                    System.out.println("key = " + str + ", val = " + val);
                }
                break;
            case 2:
                String val = longestPalindrome(tests[8]);
                System.out.println("key = " + tests[8] + ", val = " + val);
                break;
        }
        System.out.println(System.currentTimeMillis() - st + " ms");
    }

    private String longestPalindrome(String str) {
        if (str == null || "".equals(str.trim())) return "";


        String max = "" + str.charAt(0);
        for (int i = 0; i < str.length() - 1; i++) {
            String s = null;
            if (i + 2 < str.length() && str.charAt(i) == str.charAt(i + 2)) {
                s = getPalindrome(str, i, 1);
            }

            if (str.charAt(i) == str.charAt(i + 1)) {

                String s2 = getPalindrome(str, i, 2);
                if (s != null && s2.length() > s.length()) {
                    s = s2;
                } else if (s == null) {
                    s = s2;
                }
            }

            if (s != null && s.length() > max.length()) {
                max = s;
            }
        }

        return max;
    }

    private String getPalindrome(String str, int i, int type) {
        int start;
        int end;
        if (type == 1) {
            start = i;
            end = i + 2;
        } else {
            start = i;
            end = i + 1;
        }

        while (start > 0 && end + 1 < str.length() && str.charAt(start) == str.charAt(end)) {
            start--;
            end++;
        }

        if (str.charAt(start) != str.charAt(end)) {
            start++;
            end--;
        }
        return str.substring(start, end + 1);
    }
}